package leetcode.tree_problem;

/**
 * 236. 二叉树的最近公共祖先
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
 */
public class 二叉树的最近公共祖先L2 {
    TreeNode nearNode ;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        findBoolean(root , p ,q);
        return nearNode;
    }
    public boolean findBoolean(TreeNode root, TreeNode p, TreeNode q){
        //看一下这个树里面是不是包含有p或q，捎带着就把最近祖先求出来了，回溯的时候；
        if (root == null){
            return false;
        }

        //看左子树中有吗有的话
        int left = findBoolean(root.left , p , q) ? 1 : 0;
        int right = findBoolean(root.right , p ,q) ? 1 : 0;//处理右子树
        int mid = (root == p || root == q) ? 1 : 0;//处理看根是啥情况包含不

        if (left + right + mid == 2){
            nearNode = root;
        }
        return (left + right + mid) > 0;



    }
}
